import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-07
 * Time:14:18
 */
/**
 *如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
 *
 * 给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
 *
 * s 是一个尽可能长的快乐字符串。
 * s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
 * s 中只含有 'a'、'b' 、'c' 三种字母。
 * 如果不存在这样的字符串 s ，请返回一个空字符串 ""
 * */
/**
 * 贪心算法
 *具体的，可以使用「优先队列（堆）」来实现上述过程，以 （字符编号, 字符剩余数量） 的二元组形式进行存储，构建以 字符剩余数量 排倒序的「大根堆」：
 *
 * 起始先将 (0, a)(0,a)、(1, b)(1,b) 和 (2, c)(2,c) 进行入堆（其中 123 为字符编号，代指 abc，同时规定只有剩余数量大于 0 才能入堆）；
 * 每次取出堆顶元素（剩余数量最多的字符），尝试参与答案的构造：
 * 不违反连续三个字符相同：则说明当前字符能够追加到当前答案尾部，若追加后还有字符剩余，则更新剩余数量重新入堆；
 * 违反连续三个字符相同：说明该字符无法追加到当前答案尾部，此时尝试从堆中取出剩余次数次大的字符（若当前堆为空，说明没有任何合法字符能够追加，直接 break），若次大字符追加后还有字符剩余，则更新剩余数量重新入堆，同时将此前取的最大字符元祖也重新入堆；
 * 重复步骤 2，直到所有字符均被消耗，或循环提前结束。
 *
 * 该做法的正确性：当 a = b = c \=0 时能够确保所有字符轮流参与构建，得到长度最大的快乐字符串，而该贪心策略（每次尽可能地进行大数消减）
 * 可以确保能够尽可能的凑成 a = b = ca=b=c 的局面，并且凑成该局面过程中不会从有解变为无解
 */
public class TestDemo1 {
    public String longestDiverseString(int a, int b, int c) {
        //建立优先级堆列;按大堆建立
        PriorityQueue<int[]> queue = new PriorityQueue<>(3, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });
        if (a > 0) {
            //0+'a' = 'a'
            queue.add(new int[]{0, a});
        }
        if (b > 0) {
            //1+'a' = 'b'
            queue.add(new int[]{1, b});
        }
        if (c > 0) {
            //2+'a' = 'c';
            queue.add(new int[]{2, c});
        }
        StringBuilder s = new StringBuilder();
        //如果堆列空了 则排列完毕
        while (!queue.isEmpty()) {
            //抛出剩下最多的字符
            int[] cur = queue.poll();
            int n = s.length();//记录字符串长度
            //符合字符串长度大于2,且当且字符跟前面的两个字符都相同才能进入
            if (n >= 2 && s.charAt(n - 1) - 'a' == cur[0] && s.charAt(n - 2) - 'a' == cur[0]) {
                //判断堆列是否为空;为空则说明排列结束,没有其他字符了
                if (queue.isEmpty()) {
                    break;
                }
                //找出第二多的字符
                int[] next = queue.poll();
                s.append((char) (next[0]+'a'));
                //将字符数量减1后还有剩余 则将其重新入堆
                if (--next[1] != 0) {
                    queue.add(next);
                }
                //将没用到的字符入堆;
                queue.add(cur);
            } else {
                //字符串少于2或者前面的两个字符跟即将加入的字符不重复才能进入该条件
                //拼接字符
                s.append((char) (cur[0] + 'a'));
                //将字符数量减1后还有剩余 则将其重新入堆
                if (--cur[1] != 0) {
                    queue.add(cur);
                }
            }
        }
        return s.toString();
    }
}
